package graph.algo;

import graph.model.Graph;

import java.util.LinkedList;
import java.util.Queue;

public class BFS {

	Graph graph;

	public BFS(Graph graph) {
		this.graph = graph;
	}

	public void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();

		graph.getVertices()[0].setVisited(true); // start with the first
													// vertex
		graph.displayVertex(0); // display it
		queue.add(0); // add it to the queue

		int v2;
		while (!queue.isEmpty()) { // till queue is empty

			int v = queue.poll(); // remove the vertex at the head
			// Until v has not unvisited neighbors
			while ((v2 = graph.getAdjUnVisitedVertex(v)) != -1) {
				graph.getVertices()[v2].setVisited(true);
				graph.displayVertex(v2);
				queue.add(v2);
			}

		}

		// Reset
		//graph.resetVisited();
	}
	
	public static void main(String[] args) {

		Graph graph = new Graph(5, 4, false, false);
		graph.addVertex(0, 'A');
		graph.addVertex(1, 'B');
		graph.addVertex(2, 'C');
		graph.addVertex(3, 'D');
		graph.addVertex(4,  'E');
		
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(0, 3);
		graph.addEdge(3, 4);

		System.out.println("Visits:");
		BFS bfs = new BFS(graph);
		bfs.bfs();
		System.out.println();
	}
}
